
public class StackSorter {
	public static int compare (String a, String b){
		return a.compareTo(b);
	}
	
	public synchronized static long insertionSort (Pilha p){
		long start, end;
		
		Pilha pilha = new Pilha();
		pilha.setTop(p.getTop());
		pilha.setSize(p.getSize());
		
		Pilha tmpCompare = new Pilha();
		Pilha pilhaOrder = new Pilha();
		int N = pilha.getSize();
		String key = new String();
		String aux = new String();
			
		// Impressao da pilha desordenada
		int sizePilhaOrder = pilha.getSize();
		System.out.print("Antes: ");
		for (int j = 0; j < sizePilhaOrder; j++)
			System.out.print(pilha.pop() + " ");
		
		pilha.setTop(p.getTop());
		pilha.setSize(p.getSize());
		
		start = System.currentTimeMillis();
		
		while (pilhaOrder.getSize() != N){
			key = pilha.pop();
			while (!pilha.isEmpty()){
				aux = pilha.pop();
										
				if (compare(key, aux) == -1){
					tmpCompare.push(key);
					key = aux;
				}
				else
					tmpCompare.push(aux);
			}
			
			pilhaOrder.push(key);
			
			pilha.setTop(tmpCompare.getTop());
			pilha.setSize(tmpCompare.getSize());
			tmpCompare.setTop(null);
			tmpCompare.setSize(0);
		}
		end = System.currentTimeMillis();
		
		// Impressao da pilha ordenada
		sizePilhaOrder = pilhaOrder.getSize();
		System.out.print("\tDepois: ");
		for (int j = 0; j < sizePilhaOrder; j++)
			System.out.print(pilhaOrder.pop() + " ");
		System.out.println("");
		
		return end - start;
	}
}
